package com.yang.Hash_;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class LeetCode18 {
    public static void main(String[] args) {
        int[] nums = {1,0,-1,0,-2,2};
        int target = 0;
        SolutionLeetCode18 solutionLeetCode18 = new SolutionLeetCode18();
        List<List<Integer>> lists = solutionLeetCode18.fourSum(nums, target);
        Iterator<List<Integer>> iterator = lists.iterator();
        for (Iterator<List<Integer>> it = iterator; it.hasNext(); ) {
            List o = it.next();
            System.out.println(o);
        }
    }
}

class SolutionLeetCode18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        ArrayList<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {

        if ( nums[i] > target && (nums[i] >=0 || target >= 0) ){
            continue;
        }
            // 注意顺序问题！！nums[i-1]若是放在前面就会报错 因为 i>0在后面这个条件最后才判断
          if ( i > 0 && nums[i] == nums[i-1] ){
              continue;
          }

            for (int j = i+1; j < nums.length; j++) {
                if (nums[j] == nums[j-1] && j > i+1){
                    continue;
                }
                // 注意这里是j+1 !!! 如果忽略了这个条件那就会多出几个数据
                int left = j+1, right = nums.length-1;

                while (right > left){
                    int sum = nums[i] + nums[j] +nums[left] +nums[right];
                    if(sum > target){
                        right--;
                        while (right > left && nums[right] == nums[right+1]) right--;
                    }else if (sum < target){
                        left++;
                        while (right > left && nums[left] == nums[left-1]) left++;
                    }else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while ( left < right && nums[left] == nums[left+1]) left++;
                        while ( right > left && nums[right] == nums[right-1]) right--;
                        // 注意这里是当完成一次添加后进行坐标的移动，不要放到else外面了！ 那样每次循环都会移动一次坐标！
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}
